package cn.whdream.datastructure.search;

import java.util.Arrays;

/**
 * 
 * @author blackjuly
 * 斐波那契数列查找算法  不太好理解，需要后期深挖一下
 * TODO 需要重新理解整理一下，为了速度暂时搁置；最后统一清算
 */
public class FibonacciSearch {
	private static final int MAX_SIZE = 20;

	public static void main(String[] args) {
		int[] arr = {1,8,10,89,1000,1234};
		System.out.println("index :"+fibSearch(arr, 1234));
	}
	
	public static int[] fib() {
		int[] f = new int[MAX_SIZE];
		f[0] = 1;
		f[1] = 1;
		for (int i = 2; i < f.length; i++) {
			f[i] = f[i-1] + f[i-2];
		}
		return f;
	}
	/**
	 * 
	 * @param arr 数组
	 * @param key 需要查找值
	 * @return
	 */
	public static int fibSearch(int[] arr ,int key) {
		int low = 0;
		int high = arr.length - 1;
		int k = 0;//表示斐波那契的分割数值的下标
		int mid = 0;
		int f[] = fib();//获取数列
		//获取分割数值的下标
		while(high > f[k] - 1) {
			k++;
		}
		int[] temp = Arrays.copyOf(arr, f[k]);
		for (int i = high + 1; i < temp.length; i++) {
			temp[i] = arr[high];
		}
		
		while(low <= high) {
			mid = low + f[k-1] -1;
			if(key < temp[mid]) { //向数组在
				high = mid - 1;
				//1. 全部元素 = 前面的元素 + 后面的元素
				//f[k] = f[k-1] + f[k-2] + f[k-3]
				//即在 f[k - 1 ] 继续查找 
				k--;
			} else if( key > temp[mid]) {
				low = mid + 1;
				//全部 = 前 + 后
				
				k -= 2;
			}else {
				//确定返回的是哪个下标
				if(mid <= high ) {
					return mid;
				}else {
					return high;
				}
			}
		}
		
		return -1;
	}
}

